#ifndef SORT_INSERTION_HPP
#define SORT_INSERTION_HPP

#include "../common.hpp"

YFWZ100_NS_BEGIN

template <typename T>
void insertion_sort(T arr[], int start, int end)
{
  for (size_t i = start + 1; i < end; i++) {
    // 从后往前遍历，找到当前元素的排序位置，进行插入
    int j = i - 1;
    auto t = arr[i];
    for (;j >= start && t < arr[j]; j --) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = t;
  }
}

template <typename PointerLike>
void insertion_sort(PointerLike start, PointerLike end)
{
  for (PointerLike i = start + 1; i != end; i++) {
    for (PointerLike j = i - 1; j >= start && *(j + 1) < *j; j --) {
      swap(*(j + 1), *j);
    }
  }
}

YFWZ100_NS_END

#endif//SORT_INSERTION_HPP
